[plt-scheme] The Swine Before Perl

From: Ryan Culpepper (ryan_sml at yahoo.com)
Date: Mon Jul 10 02:10:08 EDT 2006

--- Jaime Vargas <jev at mac.com> wrote:

> After listening to the excellent presentation by Shriram, I asked  
> myself, what it will take to extent the automaton to perform
> actions  
> on each state transition. So starting with:
> 
> (automaton init
>                (init : (c -> loop))
>                (loop : (a -> loop)
>                        (d -> loop)
>                        (r -> end))
>                (end  : (r -> end)))
> 
> I wanted,
> 
> (automaton init
>                (init : (c -> loop))
>                (loop : (a -> loop do count)
>                        (d -> loop)
>                        (r -> end))
>                (end  : (r -> end)))

>From your example, I infer that you want the syntax of automaton to
look like this:

Automaton ::= 
  (automaton name (label : (input -> . Transition) ...) ...)
Transition ::= (label)
            |  (label _do_ expression)

I would rewrite the pattern of the automaton macro as above (note the
dot!) and introduce a new macro that interprets the transition:

(define-syntax automaton
  (syntax-rules (-> : do)
    ((_ init-state
        (state : (cndn -> . transition) ...) ...)
     (letrec ([state
               (lambda (stream)
                 (or (empty? stream)
                     (case (first stream)
                       [(cndn)
                        (do-transition transition (rest stream))]
                       ...
                       [else false])))]
              ...)
       init-state))))

(define-syntax do-transition
  (syntax-rules (do)
    [(_ (new-state) stream)
     (new-state stream)]
    [(_ (new-state do action) stream)
     (begin (action) (new-state stream))]))

Your attempt using syntax-case, below, fails because you still only
match homogeneous sequences of transitions. More abstractly, you're
accepting (union (list-of A) (list-of B)) when you want to be
accepting (list-of (union A B)). Your macro processes the first state
successfully, because it only uses simple transitions. It fails on
the first state (loop) that uses both simple transitions and
transitions with actions.

Ryan

> So in search for answer, I read a bit about syntax-case and
> cousins, and I arrived to something that almost works.
> 
> (define-syntax automaton
>    (lambda (stx)
>      (syntax-case stx ()
>        [(_ init transitions ...)
>         (with-syntax
>             ([bindings
>               (letrec
>                   ([lot (syntax->list (syntax (transitions ...)))]
>                    [create-bindings
>                     (lambda (t)
>                       (if (null? t)
>                           '()
>                           (cons
>                            (syntax-case (car t) (-> : do)
>                              [(state : (cndn -> new-state do  
> action) ...)
>                               (syntax
>                                [state
>                                 (lambda (stream)
>                                   (or (empty? stream)
>                                       (case (first stream)
>                                         [(cndn) (action) (new-state
>  
> (rest stream))]
>                                         ...
>                                         [else false])))])]
>                              [(state : (cndn -> new-state) ...)
>                               (syntax
>                                [state
>                                 (lambda (stream)
>                                   (or (empty? stream)
>                                       (case (first stream)
>                                         [(cndn) (new-state (rest  
> stream))]
>                                         ...
>                                         [else false])))])])
>                            (create-bindings (cdr t)))))])
>                 (create-bindings lot))])
>           (syntax
>            (letrec bindings init)))])))
> 
> However, it is not handling the transition.
> 
> (automaton init
>         (init : (c -> loop))
>         (loop : (a -> loop do count)
>                 (d -> loop)
>                 (r -> end))
>         (end  : (r -> end)))
> 
> which fails with "loop: bad syntax in: (loop : (a -> loop do count)
>  
> (d -> loop) (r -> end))".
> 
> It seems that the transition ... is not being handle correctly,
> or am I missing something? Also, Is there a simpler way to
> write this type automaton macro?
> 
> Thanks for the help. -- Jaime
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> 



Posted on the users mailing list.