Scheme: FSM substring search

Question

I have been working on a function that return a FSM that searches a specific word based on the argument of the constructor. The idea was to use those routines as means to learn about regular expressions and maybe implement a very basic regexp system, so I thought that matching normal string was a good first step in that direction.

This is actually my first "complex" program in Scheme. I learnt to program in C so it has been a little hard to switch my way of thinking into a functional approach, so any comments in my way of programming in Scheme would also be very useful.

NOTES:

1. I know that using lists might not be the most efficient thing to do, but they allowed me to program in a more functional way without using vector-set!

2. If there is something to add or to fix please don't just put the answer, that way I won't learn. Try to use code only if necessary.

3. Sadly Emacs uses tabs for indentation so formatting may be a little messy.

An automata in my code is represented as a list of states where each one is described as a pair of the form (a . b) where a is the matched character and b is the index of the state it transitions to. If no pair contains a specific character then it defaults to the invalid state (index = 0).

The run-automata function searches a matching substring and returns its offset or #f if it is not contained inside string.

(define (string-null? s) (= (string-length s) 0))
(define (string-append-c s c) (string-append s (string c)))
(define (string-tail str) (substring str 1 (string-length str)))

;; is s2 a prefix of s1?
;; [TODO] - Use offset instead of string-tail
(define (string-prefix? s1 s2)
  (cond 
    [(string-null? s2) #t]
    [(string-null? s1) #f]
    [(not (char=? (string-ref s2 0)
                  (string-ref s1 0))) #f]
    [else (string-prefix? (string-tail s1)
                          (string-tail s2))]))


(define (enumerate start end)
  (define (iter start end acc)
    (if (> start end)
        acc
        (iter start (- end 1) (cons end acc))))

  (iter start end '()))


(define (build-automata needle)
  (define (max-suffix-that-is-prefix str)
    (cond 
      [(string-null? str) ""]
      [(not (string-prefix? needle str))
         (max-suffix-that-is-prefix (string-tail str))]
      [else str]))

  (define (build-transitions state-string transitions dictionary)
    (if (null? dictionary)
        transitions
        (let* ([c (car dictionary)]
               [suffix (max-suffix-that-is-prefix (string-append-c state-string c))])
          (build-transitions 
            state-string 
            (if (string-null? suffix)
                transitions
                (cons (cons c (string-length suffix)) 
                      transitions))
            (cdr dictionary)))))

  ;; Last state does not require a transition as it is the final state.
  ;; "We are done by that point".
  (let ([dictionary (string->list "abcdefghijkmnopqrstuvwxyz")])
    (map (lambda (n) 
           (build-transitions 
             (substring needle 0 n) 
             '() 
             dictionary))
         (enumerate 0 (- (string-length needle) 1)))))


;; Takes an automata and a string and returns the offset of the pattern the
;; automata was built to search
(define (run-automata automata string)
  (define (search-transition c state-transitions)
    (cond 
      [(null? state-transitions) 0]
      [(char=? (caar state-transitions) c) (cdar state-transitions)]
      [else (search-transition c (cdr state-transitions))]))

  (define (step state automata-size offset)
    (cond 
      [(= state automata-size) (- offset automata-size)]
      [(>= offset (string-length string)) #f]
      [else (step (search-transition (string-ref string offset)
                                     (list-ref automata state))
                  automata-size
                  (+ offset 1))]))

  (step 0 (length automata) 0))

Answer 1

My suggestions are less about your design of the automaton, but rather a few comments on the style and language which I hope you will find useful.

Know your functions
Note that, string-null? is #t if the string has zero length. Thus, if ((string-null? str) "") is the same as if ((string-null? str) str). And that combines well with the else part in max-suffix-that-is-prefix which also returns str.

  (define (max-suffix-that-is-prefix str)
    (if (string-prefix? needle str)
        str
        (max-suffix-that-is-prefix (string-tail str))))

Named let
I noticed that some functions (enumerate and run-automata) define local functions only to then call them with initial values. Scheme provides a syntactic form for that, the named let:

(let proc-id ([id init-expr] ...) body ...+)

More on named let: https://docs.racket-lang.org/reference/let.html

Adhering to the declarative paradigm
The enumerate function could be written in a declarative style. To enumerate from start to end is to cons start to the enumeration from (+ start 1) to end.

(define (enumerate start end)
  (if (= start end)
      `(,end)
      (cons start (enumerate (+ start 1) end))))

Note, however, that this is not an equivalent formulation of the iterative style using an accumulator since the call the enumerate in the call to cons prevents tail-recursion optimisation.

Cleaner syntax using a named let:

(define (enumerate start end)
  (let iter ([start start] 
             [end end] 
             [acc '()])
    (if (> start end)
        acc
        (iter start (- end 1) (cons end acc)))))