# Scheme: FSM substring search

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


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.

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

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)))))
`
• Thanks for your comments. I didn't know about named let which I find now very useful as I had that recurring problem of declaring functions just to call them with the initial arguments. What I don't understand completely is, what do you mean by "adhering to the declarative paradigm". I did know the alternative way to enumerate, but I went with this one specifically because of the tail-recursion optimization. I would like to understand your point though. – Thomas Jan 8 '19 at 18:54
• @Thomas I brought it up because you said that you came from a C background and sometimes have difficulties to switch to a functional approach. -- I can imagine it to be quite common for those who come from an imperative paradigm to think in terms of loops and conditionals and then try to write that with the means available in e.g. Scheme. That would result in codes using such auxiliary functions to iterate. But if you did it intentionally and for a good reason, than it is quite all right ^^ – jgb Jan 9 '19 at 7:17