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?