On Mar 9, 2012, at 11:00 AM, Rüdiger Asche wrote:
> see my responses to Matthias for that)
I didn't see a response.
> ... so I wonder what a more natural or Schemish way there wsould be to tackle
> such an issue…
Here is what I had in mind:
#lang racket
#| you write things like this:
(define-fsm ab*c
;; alphabet, with mapping to external events
([A 1][B 2][C 3])
;; states:
(start seenA seen1B seenC)
(start)
(seenC)
(on A: start -> seenA)
(on B: seenA -> seenB)
(on C: seenB -> seenC))
;; the macro expands to something like this:
|#
(define (driver event-stream)
(define (start letter)
(if (= letter 1) seenA (error "fsm1")))
(define (seenA letter)
(if (= letter 2) seenB (error 'fsm2 "~e" letter)))
(define (seenB letter)
(cond
[(= letter 2) seenB]
[(= letter 3) seenC]
[else (error 'fsm3 "~e" letter)]))
(define (seenC letter)
(error "fsm: final state"))
(let loop ([es event-stream][current-state start])
(if (eq? current-state seenC)
"accepted"
(loop (remaining es) (current-state (next es))))))
;; one way to implement functional event stream:
(define remaining rest)
(define next first)
;; -----------------------------------------------------------------------------
(driver '(1 2 2 2 2 3))
;; -----------------------------------------------------------------------------
NOW: measure. I chose to represent functions as states for the heck of it.
You could imagine a big fat loop instead. You could imagine a big fat vector
of vectors instead to represent the transition matrix. The important thing
is you have
(1) a text-book looking notation for FSMs
(2) you measure high-level performance issues not in-lining of numbers,
which is a ternary bit at best.
For all you know, the Racket compiler produces the best possible code with
function pointers (as I have done) not with a transition matrix. Or perhaps
you have many FSMs, some work best with function pointers (for the density
of representation) and others work better with a transition matrix (because
the graph is dense). You can choose at expansion time, which representation
you want
and yet you always write down text-book FSMs.
-- Matthias
____________________
Racket Users list:
http://lists.racket-lang.org/users
