;; A little experiment with finite state automaton.
;;
;; Danny Yoo (dyoo@hkn.eecs.berkeley.edu)
;;
;; First, let's copy and paste the automaton definition from Shriram
;; Krishnamuthi's paper "Automata via Macros":
;;
;; http://www.cs.brown.edu/~sk/Publications/Papers/Published/sk-automata-macros/
;;
(module automaton mzscheme
  (require (lib "list.ss"))

  (provide automaton aho-corasick-automaton)


  (define-syntax automaton
    (syntax-rules (:)
      [(_ init-state
          (state : response ...)
          ...)
       (let-syntax
           ([process-state
             (syntax-rules (accept ->)
               [(_ (accept))
                (lambda (stream)
                  (cond
                   [(empty? stream) #t]
                   [else #f]))]
               [(_ ((label -> target) (... ...)))
                (lambda (stream)
                  (cond
                   [(empty? stream) #f]
                   [else
                    (case (first stream)
                      [(label) (target (rest stream))]
                      (... ...)
                      (else #f))]))])])
         (letrec ([state
                   (process-state (response ...))]
                  ...)
           init-state))]))


  
  ;; The idea here is that we want to adjust this macro to allow for
  ;; fail transitions.

  (define-syntax aho-corasick-automaton
    (syntax-rules (:)
      [(_ init-state
          (state : response ...)
          ...)

         (letrec ([state
                   (aho-corasick-process-state (response ...))]
                  ...)
           init-state)]))


(define-syntax aho-corasick-process-state
  (syntax-rules (accept ->)
    [(_ (accept accept-expr))
     (lambda (stream)
       (cond
        [(empty? stream) accept-expr]
        [else #f]))]
    [(_ ((label -> target) (... ...)))
     (lambda (stream)
       (cond
        [(empty? stream) #f]
        [else
         (case (first stream)
           [(label) (target (rest stream))]
           (... ...)
           (else #f))]))]))  
  )