[racket] Finite State Machines of Arbitrary Size using Racket's composable control

From: Galler (lzgaller at optonline.net)
Date: Thu May 24 13:07:05 EDT 2012


I fully agree with you that any FSM is equivalent to functional 
composition and can be implemented in the manner you show.

However , in the way you've implemented the signal-handlers

  (define (B i)
>       (if (= 0 (get i))
>         (begin (printf "~s)" (sub1 i))
>                (next A i))

I believe you have the signal handler B both reading the signal (get i) 
and advancing to the next position in the signal-stream (next A i)

Whereas the method I presented with composable continuations separates

1) reading the signal

2) processing the signal in the signal-handlers

3) moving to the next signal in the signal stream

4) transitioning between states

Let me sit down tonight and figure out if those are possible purely with 
functional composition.


On Thu, May 24, 2012 at 11:59 AM, Eli Barzilay wrote:

> More than a week ago, Galler wrote:
>> This code was generated in response to the user who sought to
>> implement run-length encoding of a bit-vector on Sunday night.
>> [...]
>> Its a good 10 second answer to "what can you do with composable 
>> control"
>> that would be impossible in its absence?
> Note that the FSM part of your code always passes around a simple tail
> continuation, which means that you could just use tail calls to do the
> same.  Here's a version of this -- I intentionally left most of it as
> in your code, except for banging the counter which isn't really
> needed.
>   (define/contract (list-of-ranges-of-ones vtr)
>     (-> (vectorof (or/c 1 0)) list?)
>     (read (open-input-string
>            (with-output-to-string
>              (λ () (display "(") (encode vtr) (display ")"))))))
>     (define (encode v)
>     (define (get i) (vector-ref v i))
>     (define last (sub1 (vector-length v)))
>     (define (next S i) (when (< i last) (S (add1 i))))
>     (define (B i)
>       (if (= 0 (get i))
>         (begin (printf "~s)" (sub1 i))
>                (next A i))
>         (next B i)))
>     (define (A i)
>       (if (= 0 (get i))
>         (next A i)
>         (begin (printf "(~s " i)
>                (next B i))))
>     (A 0))
> -- 
>           ((lambda (x) (x x)) (lambda (x) (x x)))          Eli 
> Barzilay:
>                     http://barzilay.org/                   Maze is 
> Life!

Posted on the users mailing list.