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?

About these ads

3 thoughts on “Ruby DSL to describe Automata

  1. Vc ta conseguindo me convencer da beleza do Ruby. Fiz hoje umas paradinhas nessa linguagem que ficaram muito interessante. Dá uma olhada lá no meu blog.

    De qualquer forma, mantenho minhas criticas ainda haha. Preciso de mais motivos.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s