[plt-scheme] re: Shriram Krishnamurthi's "automaton" macro from "Swine before Perl"

Hi Chris --
Looks like the immediate cause is that you refer to "new-state" without 
using an ellipsis.  (The macro doesn't know which particular new-state you're
trying to test against.)
> 
>     [(_ init-state
>         (state : (cndn -> new-state) ...) ...)
>      (letrec ([state (lambda (stream)
>                        (or (and (empty? stream)
>                                 (eq? new-state #f))   ; <-- which new-state?
>                            (case (first stream)
>                              [(cndn)
>                               (new-state (rest stream))]
>                              ...
>                              [else false])))]
>               ...)
>        init-state)]))
> 
You want to move your test for #f from the entire-current-state level
to within the individual transition cases.
I think what you were trying would have to be:

  (letrec ([state (lambda (stream)
                     (if (empty? stream)                    ; Discuss below.
                         false
                         (case (first stream)
                           [(cndn)
                            (if (empty? (rest stream))      ; No more inputs?
                                (eq? new-state false)       ; next state exists?
                                (new-state (rest stream)))] ; else proceed
                           ...
                           [else false])))]
           ...)
    init-state)

...Hmm, that rubs the wrong way though, to check for empty stream
in two different places: at the top-level, and then checking (rest stream)
before recurring.  Yuck.


Instead, if you are happy with indicating acceptance by saying
"the automaton must end in a state with no outgoing transitions" 
(like the example), then this will work:

(define-syntax automaton
  (syntax-rules (-> :)
    [(automaton init-state
       (state : (cndn -> new-state) ...) ...)

     (letrec ([state (lambda (stream)
                       (if (empty? stream)                ; No more inputs?
                           (empty? '(new-state ...))      ; In a terminal state?
                           (case (first stream)           ; Proceed..
                             [(cndn)
                              (new-state (rest stream))]
                             ...
                             [else false])))]
              ...)
       init-state)]))

I was about to say this feels hackish -- using quote to
create '(new-state ...), which feels like it's back up on the syntax level,
asking if the macro pattern has matched any arguments.
But I guess it's actually fine -- it's just creating a list of next-states,
so no problem asking if that's empty.


This forces your final-state to be a sink though.  A more complete sol'n
would be to augment the macro with a keyword for final-states (which 
can then be allowed as intermediate states as well).
But in that case, I  don't see an easy way to use
this letrec solution any more: there wouldn't be just one
pattern states, but there'd be two patterns, handled in separate
branches of syntax-rules, and so a single letrec doesn't seem to work.
...But I'm newer to macros, so maybe I'm missing something;
if somebody does have a letrec sol'n once you've added a final-state 
keyword, I'd be interested in seeing it!

Cheers,
ian


> From: "Chris Wright" <wrightca at hotmail.com>
> To: plt-scheme at list.cs.brown.edu
> Date: Mon, 08 Nov 2004 21:50:22 +1100
> Subject: [plt-scheme] Shriram Krishnamurthi's "automaton" macro from "Swine b
>   efore Perl"
> 
> Hi.
> 
> I think I understand Shriram's macro:
> 
> (define-syntax automaton
>   (syntax-rules (-> :)
>     [(_ init-state
>         (state : (cndn -> new-state) ...) ...)
>      (letrec ([state (lambda (stream)
>                        (or (empty? stream)
>                            (case (first stream)
>                              [(cndn)
>                               (new-state (rest stream))]
>                              ...
>                              [else false])))]
>               ...)
>        init-state)]))
> 
> (define a
>   (automaton init
>              (init : (c -> loop))
>              (loop : (a -> loop)
>                      (d -> loop)
>                      (r -> end))
>              (end : )))
> 
> In use:
> 
> Welcome to DrScheme, version 208.
> Language: Pretty Big (includes MrEd and Advanced).
> >(a '(c a r))
> #t
> >(a '(c d a r))
> #t
> >(a '(c x))
> #f
> 
> but:
> >(a '(c a d a))
> #t
> 
> 
> As an exercise, I thought I'd try seeing if I could make it check that when 
> the stream is empty, new-state is null, and I'm having trouble with my 
> ellipses!
> 
> (define-syntax automaton
>   (syntax-rules (-> :)
>     [(_ init-state
>         (state : (cndn -> new-state) ...) ...)
>      (letrec ([state (lambda (stream)
>                        (or (and (empty? stream)
>                                 (eq? new-state #f))
>                            (case (first stream)
>                              [(cndn)
>                               (new-state (rest stream))]
>                              ...
>                              [else false])))]
>               ...)
>        init-state)]))
> 
> (define a
>   (automaton init
>              (init : (c -> loop))
>              (loop : (a -> loop)
>                      (d -> loop)
>                      (r -> end))
>              (end : #f)))
> 
> This gives:
> 
> syntax: too few ellipses for pattern variable in template in: new-state
> 
> (And I'm not even sure that the test (eq? new-state #f) will do what I want 
> it too, but that's a separate issue)
> 
> 
> Could someone help me understand this?
> 
> Thanks very much.
> 
> Chris Wright