[racket] Finite State Machines of Arbitrary Size using Racket's composable control
Galler
run-length encoding of a bit-vector on Sunday night.
I didn't post this to the board b/c there's a much easier way to solve
problem using regular expressions, which Eli B. demonstrated.
But, the (infinite-k-pump) function strikes me as a correct and complete
way to implement finite state machines (FSM) of aribtrary size in racket
using composable control.
Its a toy, but maybe of some pedagogical use.
Jay's web server works essentially the same way, though instead of
one-byte signals, he's using
http-requests.
Its a good 10 second answer to "what can you do with composable control"
that would be impossible in its absence?
R./
Zack
#lang racket
;Finite State Machine of arbitrary size using composable control
(require racket/control
rackunit
rackunit/text-ui)
(define/contract (list-of-ranges-of-ones vtr)
(-> (vectorof (or/c 1 0)) list?)
(read (open-input-string (with-output-to-string (λ _
(display "(")
(encoding-scheme-helper (prompt (infinite-k-pump))
(vector->list (vector-append vtr #(0))))
(display ")"))))))
;recursive function. Note the prompt which is how far the invocation of
abort, in (infinite-k-pump) wipes out stack
(define (encoding-scheme-helper kont lst)
(unless (null? lst)
(encoding-scheme-helper (prompt (kont (car lst)))
(cdr lst))))
(define (infinite-k-pump)
(let ((counter 0))
(letrec ((incr-counter (λ _ (set! counter (add1 counter))))
(B (λ (signal)
(if
(= signal 0)
(begin (display (sub1 counter)) (display ")")
(incr-counter)
(A (let/cc k (abort k))))
(begin (incr-counter)
(B (let/cc k (abort k)))))))
(A (λ (signal)
(if
(= signal 0)
(begin (incr-counter)
(A (let/cc k (abort k))))
(begin (display "( ") (display counter) (display "
")
(incr-counter)
(B (let/cc k (abort k))))))))
;init function is A
(A (let/cc k (abort k))))))
;(run-tests does-it-work?)
; 12 success(es) 0 failure(s) 0 error(s) 12 test(s) run
(define does-it-work?
(test-suite
"Tests for FSM"
(check-equal? (list-of-ranges-of-ones #(0)) '())
(check-equal? (list-of-ranges-of-ones #(0 0))'())
(check-equal? (list-of-ranges-of-ones #(0 0 0)) '())
(check-equal? (list-of-ranges-of-ones #(1)) '((0 0)))
(check-equal? (list-of-ranges-of-ones #(1 1)) '((0 1)))
(check-equal? (list-of-ranges-of-ones #(1 1 1)) '((0 2)))
(check-equal? (list-of-ranges-of-ones #(1 1 1 0)) '((0 2)))
(check-equal? (list-of-ranges-of-ones #(0 1 1 1)) '((1 3)))
(check-equal? (list-of-ranges-of-ones #(0 1 1 1 0)) '((1 3)))
(check-equal? (list-of-ranges-of-ones #( 0 1 1 1 0 0 0 1 1 1 0)) '((1
3)
(7 9)))
(check-equal? (list-of-ranges-of-ones #( 1 1 1 1 0 0 0 1 1 1 1)) '((0
3)
(7 10)))
(check-equal? (list-of-ranges-of-ones #( 0 1 0 1 0 1 0 1 0 1 0)) '((1
1)
(3 3) (5 5) (7 7) (9 9)))))
____________________
Racket Users list:
http://lists.racket-lang.org/users
Marijn
Hash: SHA1
Hi Zack,
On 15-05-12 18:56, 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.
>
> I didn't post this to the board b/c there's a much easier way to
> solve problem using regular expressions, which Eli B.
> demonstrated.
>
> But, the (infinite-k-pump) function strikes me as a correct and
> complete way to implement finite state machines (FSM) of aribtrary
> size in racket using composable control.
It seems that this function as you present it below is just the
2-state state-machine that solves the problem of that user, but that
it could be used as a template for how to implement arbitrary (larger)
FSMs.
> Its a toy, but maybe of some pedagogical use.
>
> Jay's web server works essentially the same way, though instead of
> one-byte signals, he's using http-requests.
Interesting. That would be the webserver that's built in to Racket right?
> Its a good 10 second answer to "what can you do with composable
> control" that would be impossible in its absence?
Unfortunately my grasp on composable control is tenuous at best, so
this 10 second answer goes over my head :(. In what way is this
solution impossible without it? I mean FSMs can be implemented without
it (and not just in the theoretical Turing-complete tarpit way).
Marijn
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.19 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iEYEARECAAYFAk+57v8ACgkQp/VmCx0OL2yIBgCdGzqbOwJjBeKUrQgdYI4BcLwV
alUAmgMY4pm1cqy42e0Swy6g4tpvW/Pj
=RuYb
-----END PGP SIGNATURE-----
Galler
my attempt at an answer:
Yes, just the two-state machine is presented, but could be used for
larger FSMs.
And, yes, that would be the webserver that is provided with racket.
>> In what way is this solution impossible without it?
I represent the solution provides the following features which are
absent or difficult to implement in typical FSMs
1) no state variables, which has positive implications for threading and
scalability.
2) Related to item (1) the state of the machine is uniquely represented
by the continuation which takes the next signal as its redex
(i.e. (kont (car lst))) in function encoding-scheme-helper) **and
nothing else**.
3) transitions between states are managed entirely by the control
primitives abort and prompt and require no user code.
4) processing a signal by invoking (prompt (kont (car lst))
automatically results in a state transition
(even if just a self-transition) so long as the last statement executed
in a signal handler is an abort.
5) notational & representational fidelity with the problem being
modelled. This point is subjective, but I think the notation for the
signal-handlers associated with each statein infinite-k-pump is clear,
readable, and laconic.
6) A FSM built in this way can easily halt between signals. Jay's done
exactly this with his webserver.
I hope this is helpful and not too subjective. Let me know if
additional clarity desired.
R./
Zack
Eli Barzilay
> 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!
Stephen Bloch
On 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.
Stephen Bloch
sbl...@adelphi.edu
Galler
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.
R./
Zack
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
____________________
Eli Barzilay
> Eli,
>
> 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)
(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))))
(if (= 0 signal)
B))
(define (A signal i)
(if (= 0 signal)
A
(begin (printf "(~s " i)
B)))
(for/fold ([state A]) ([signal (in-vector v)] [i (in-naturals)])
(state signal i)))
But it seems redundant since the abstraction was practically there in
`next'.
Galler
Eli Barzilay
tail-calls:
http://en.wikipedia.org/wiki/Tail_call#Through_trampolining
Galler
2012?