[racket] eginner's question on elementary textual replacement...

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