代码之家 › 专栏 › 技术社区 › Mark Bolusmjak

按程序填写计划中的Letrec。宏还是EVAL?

scheme macros

Mark Bolusmjak · 技术社区 · 15 年前

我只是在玩NFA的弦乐识别。我有一个宏,它创建了一个函数,该函数使用输入并将其余的函数传递给其他一些函数。因为在我的NFA图中可能会有循环,所以我使用letrec把所有的东西放在一起。以下是一些代码(在PLT方案中进行了测试):

(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。

3 回复 | 直到 15 年前

Jason Orendorff 15 年前

如果在编译时就知道这个列表(我的意思是,在程序开始运行之前),那么可以使用宏。否则你必须使用 eval .

没关系。这是好的用于评估。:)

Jérémie Koenig 15 年前

我想出了这个宏,它似乎能完成这项工作。 (我也不是专家):

(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 )区分这些中间形式直接使用宏。

FooBee 12 年前

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

编写一个使用NFA描述并自动生成NFA的宏 ,我称之为宏 制作NFA
将make nfa应用于程序生成的列表 ,我称之为宏 应用宏指令

第二个子问题很简单:

(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宏是实现apply宏的更好方法。