Ruby DSL to describe Automata

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?

Brazilian Rails RejectConf SP’07

Unfortunately, we still have few events related to Ruby on Rails here in Brazil. Fabio Akita started the movement to change it.

We are organizing an event here in São Paulo – Brazil (link pt-BR), similar to RejectConfs. It will happen on November 17, 2007.

If you are close to São Paulo this day, do not miss it.

Update: rubyonrailsworkshops.com is now listing our event and Geoffrey Grosenbach talked about it in his last Ruby on Rails podcast. Great.