Fabio Kung

Recently, I built an internal DSL using Scheme to describe Deterministic Finite State Automata. It was quite easy to do through Scheme Macros, whose are really powerful (and hard to understand). The article “S. Krishnamurti. Automata via Macros. Journal of Functional Programming, Volume 16 , Issue 3 (May 2006)” is a great reference if you want to go deeply.

A macro to describe automata in Scheme would be as:

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

Imagine it’s needed to recognize chars sequences like c[ad]*r. Such macro, would allow you to describe a recognizer automaton for these char sequences:

(define cdar-sequence?
  (automaton init
             [init : (c -> more)]
             [more : (a -> more)
                   (d -> more)
                   (r -> end)]
             [end : accept]))

Now you can test any char sequence:

(cdar-sequence? '(c a d a d r)) ; => #t
(cdar-sequence? '(c a r a d r)) ; => #f

Well, I have to do it now in Ruby. Has anyone built some Ruby internal DSL to describe automata? I really wanted to describe them such as:

automaton "recognizer" do
  initial_state :state1 do
    transition 'c', state2
    transition 'd', state3
  end

  state :state2 do
    transition 'c', state3
  end

  final_state :state3
end

I haven’t found anything and probably will make something. What do you think?