以编程方式填写Scheme中的letrec。宏还是评估？

Question

我只是用 NFA 进行字符串识别。我有一个宏，它创建一个函数，该函数消耗输入并将其余部分传递给其他一些函数。因为我的 NFA 图中可能存在循环，所以我使用 letrec 将整个事情放在一起。下面是一些代码（已在 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))

现在，如果我有一个简单的数据结构来表示我的 NFA（如列表列表）会怎样。例如

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

我的问题是：我如何将该列表转换为以前的letrec语句？我不太擅长宏，我的理解是我可能不应该使用 eval。

Answer 1

如果该列表在编译时已知（我的意思是，在程序开始运行之前），那么您可以使用宏。否则您必须使用eval。

没关系。这是 eval 的良好用途之一。 :)

Answer 2

我想出了这个宏，它似乎可以完成这项工作
（我也不是专家）：

(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])))

技巧是使用中间形式来创建“替换循环”，
并保留标识符（参见let-bindings）来区分这些中间形式
来自直接使用宏。

Answer 3

我认为你的问题可以分为2个子问题：

1. 编写一个使用NFA描述并自动生成NFA的宏，我称这个宏ma​​ke-NFA< /strong>
2. 将 make-NFA 应用于以编程方式生成的列表，我将此宏称为 apply-macro

第二个子问题很简单：

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

第一个问题，我有一个 DFA 示例，你可以自己写一个NFA：

(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

好吧，也许define-macro是实现apply-macro的更好方法。