Програмно попълване на letrec в Scheme. Макроси или eval?

Просто си играя с 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? Не съм много добър с Macros и моето разбиране е, че вероятно не трябва да използвам 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-правилата и да повтори съдържанието е нещото, с което имам проблеми. - person z5h; 14.12.2009
comment
Мисля, че казаното от Джейсън може да е правилно. Ако знам списъка по време на компилиране, мога да използвам вашия макрос, за да опростя кодирането. Ако обаче списъкът се генерира програмно, може да се наложи да използвам eval, за да го преобразувам в подходящия код по време на изпълнение. - person z5h; 14.12.2009
comment
Ако възнамерявате да манипулирате своите NFA като данни, може да е по-лесно да ги внедрите като такива и да използвате макрос само за по-лесно въвеждане, когато трябва да кодирате твърдо някои от тях в кода. Вашият летрек/макро трик обаче е страхотен :-) - 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