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

From: Eli Barzilay (eli at barzilay.org)
Date: Thu May 24 11:59:31 EDT 2012

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

  (define/contract (list-of-ranges-of-ones vtr)
    (-> (vectorof (or/c 1 0)) list?)
    (read (open-input-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.