Программно заполняем летрек в Scheme. Макросы или eval?

Я просто играю с 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.


macros scheme
person z5h    schedule 13.12.2009    source источник
comment
Из любопытства, есть ли причина, по которой match должен быть макросом, а не обычной функцией?   -  person Jérémie Koenig    schedule 13.12.2009
comment
Вызов функции вызывает оценку параметров, чего следует избегать для работы letrec.   -  person z5h    schedule 13.12.2009

Ответы (3)


arrow_upward
4
arrow_downward

Если список известен во время компиляции (я имею в виду, что до запуска вашей программы), вы можете использовать макрос. В противном случае вы должны использовать eval.

Ничего страшного. Это одно из хороших применений eval. :)

person Jason Orendorff    schedule 13.12.2009
comment
Услышав, что вы говорите, это еще раз подтверждает то, что я считал правдой. Вы получаете галочку, пока кто-нибудь не докажет обратное. - person z5h; 14.12.2009

arrow_upward
3
arrow_downward

Я придумал этот макрос, который, кажется, выполняет свою работу (я тоже не эксперт):

(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), чтобы отличать эти промежуточные формы от прямого использования макроса.

person Jérémie Koenig    schedule 13.12.2009
comment
+1. Я ценю вашу усердную работу и пример, но моя проблема в том, что мой список создается программно. Скажем, для примера он сохраняется как nfa-rules, а начало - s1. Тогда я хочу иметь возможность делать (nfa s1 nfa-rules). У меня проблемы с тем, чтобы заставить макрос сверяться внутри nfa-rules и перебирать содержимое. - person z5h; 14.12.2009
comment
Я думаю, что то, что сказал Джейсон, могло быть правильным. Если я знаю список во время компиляции, я могу использовать ваш макрос для упрощения кодирования. Однако, если список создается программно, мне, возможно, придется использовать eval, чтобы преобразовать его в соответствующий код во время выполнения. - person z5h; 14.12.2009
comment
Если вы собираетесь манипулировать своими NFA как данными, может быть проще реализовать их как таковые и использовать макрос только для упрощения ввода, когда вам нужно жестко закодировать некоторые из них в коде. Тем не менее, ваш трюк с letrec / macro хорош :-) - person Jérémie Koenig; 14.12.2009
comment
Кроме того, ни один макрос никогда не будет взаимодействовать с какой-либо переменной: они манипулируют кодом до того, как будет произведена какая-либо оценка, поэтому для них nfa-rules - это просто слово. - person Jérémie Koenig; 14.12.2009

arrow_upward
1
arrow_downward

Думаю, вашу проблему можно разделить на 2 подзадачи:

  1. напишите макрос, который использует описание NFA и автоматически генерирует NFA, я называю этот макрос make-NFA
  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.

person FooBee    schedule 07.03.2012