Krdytkyu

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 this routines as a mean 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 is it is not contained inside string.

Thanks for you time!

(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)

  )