2

I'm just playing with an NFA for string recognition. I have a macro that creates a function which consumes input and passes on the rest to some other functions. Because there might be loops in my NFA graph, I'm using letrec to put the whole thing together. Here is some code (been testing in PLT-Scheme):

(define-syntax-rule (match chars next accepting)
  ; a function that consumes a list of chars from a list l. 
  ; on success (if there's more to do) invokes each of next on the remainder of l.
  (lambda (l) 
    (let loop ((c chars) (s l))
      (cond
        ((empty? c)
         (cond 
           ((and (empty? s) accepting) #t)
           (else 
            (ormap (lambda (x) (x s)) next))))
        ((empty? s) #f)
        ((eq? (car c) (car s)) 
         (loop (cdr c) (cdr s)))
        (else #f)))))

; matches (a|b)*ac. e .g. '(a a b b a c)
(define (matches? l)
  (letrec
      ([s4 (match '( ) '()        #t)]
       [s3 (match '(c) `(,s4)     #f)]
       [s2 (match '(a) `(,s3)     #f)]
       [s1 (match '( ) `(,s2 ,s5) #f)]
       [s5 (match '( ) `(,s6 ,s7) #f)]
       [s6 (match '(a) `(,s8)     #f)]
       [s7 (match '(b) `(,s8)     #f)]
       [s8 (match '( ) `(,s1)     #f)])
    (s1 l)))


(matches? '(a c))
(matches? '(a b b b a c))
(matches? '(z a b b b a c))

Now, what if I had a simple data-structure to represent my NFA, like a list of lists. e.g.

'((s4 () () #t)
  (s3 (c) (s4) #f) 
  ...)

My question is: How would I turn that list into the former letrec statement? I'm not too good with Macros and my understanding is that I probably shouldn't be using eval.

Mark Bolusmjak
  • 23,606
  • 10
  • 74
  • 129

3 Answers3

4

If the list is known at compile time (what I mean is, before your program starts running) then you can use a macro. Otherwise you must use eval.

It's ok. This is one of the good uses for eval. :)

Jason Orendorff
  • 42,793
  • 6
  • 62
  • 96
3

I came up with this macro which seems to do the job (I'm not an expert either):

(define-syntax nfa
  (syntax-rules (let-bindings)
    ; All the let bindings have been expanded
    [(nfa start (let-bindings . bindings))
     (lambda (l) (letrec bindings (start l)))]
    ; Otherwise, expand the next binding
    [(nfa start (let-bindings . bindings) (s c n a) . rest)
     (nfa start (let-bindings (s (match 'c (list . n) a)) . bindings) . rest)]
    ; Insert the expanded bindings list
    [(nfa start states)
     (nfa start (let-bindings) . states)]))

; matches (a|b)*ac. e .g. '(a a b b a c)
(define matches?
  (nfa s1 ([s4 ( ) ()      #t]
           [s3 (c) (s4)    #f]
           [s2 (a) (s3)    #f]
           [s1 ( ) (s2 s5) #f]
           [s5 ( ) (s6 s7) #f]
           [s6 (a) (s8)    #f]
           [s7 (b) (s8)    #f]
           [s8 ( ) (s1)    #f])))

The trick is to use intermediate forms to create "subtitution loops", and reserve identifiers (cf. let-bindings) to distinguish these intermediate forms from direct usage of the macro.

Jérémie Koenig
  • 1,198
  • 6
  • 11
  • 1
    +1. I appreciate your hard work and example, but my problem is that my list is generated programatically. Say, for the sake of example it's stored as `nfa-rules` and the start is `s1`. Then I want to be able to do `(nfa s1 nfa-rules)`. Getting the macro to "peer inside" nfa-rules and iterate over the contents is the thing I have problems with. – Mark Bolusmjak Dec 13 '09 at 21:33
  • I think what Jason said could be correct. If I know the list at compile time, I can use your macro to simplify the coding. However, if the list is generated programatically, I may have to use `eval` to convert it into the appropriate code at runtime. – Mark Bolusmjak Dec 13 '09 at 21:40
  • If you're going to manipulate your NFA's as data, it might be more straightforward to implement them as such, and use a macro only for easier entry when you have to hardcode some of them in the code. Your letrec/macro trick is neat, though :-) – Jérémie Koenig Dec 13 '09 at 23:09
  • Also, no macro is ever going to "peer inside" any variable : they manipulate the code before there's any evaluation done, so as far as they're concerned, `nfa-rules` is just a word. – Jérémie Koenig Dec 13 '09 at 23:14
1

I think your problem can be seprate into 2 subproblem:

  1. write a macro that consumes a NFA description and generate a NFA automatically,I call this macro make-NFA
  2. apply make-NFA to a list generated programatically,I call this macro apply-macro

the second subproblem is easy:

(define-syntax apply-macro
  (syntax-rules ()
    ((_ macro ls)
     (eval 
      `(macro ,@ls)
      (interaction-environment)))))
;(define ls '(1 2 3))
;(apply-macro if ls)=>2

the first question,I have a DFA sample,you can write a NFA by youself:

(define-syntax make-DFA
  (syntax-rules (: ->)
    ((_ init-state (state : result (symbol -> next) ...) ...)
     (letrec 
         ((state 
           (lambda(sigma)
             (cond
               ((null? sigma) result)
               (else
                (case (car sigma)
                  ((symbol) 
                   (next (cdr sigma)))...
                  (else false))))))... )
       init-state)))) 

(define DFA1
  (make-DFA q1
             (q1 : true (#\a -> q2)
                 (#\b -> q3))
             (q2 : false (#\a -> q1)
                 (#\b -> q4))
             (q3 : false (#\a -> q4)
                 (#\b -> q1))
             (q4 : true (#\a -> q3)
                 (#\b -> q2))))
(DFA1 (string->list "ababa"));=>#f

well,may be define-macro is a better way to implement apply-macro.

FooBee
  • 778
  • 7
  • 23