Thursday, March 19, 2009

Dabbling With Generators

Some time ago, I blogged about generators, and specifically mentioned the implementation here. I've since incorporated this into my production code, and every so often find a good use for it. Today, I believe, was one of those days.

Bare with me for a moment - I'm going to try to describe the problem without mentioning any customer specific details.

Assume that you've got a list of items you want to render on the screen, such as:

(define data '(a b c d e f g)

Laying out the data in sequence is trivial. For example:

a b c d
e f g 

But, the client wanted to get fancy. He wanted, in some cases, to be able to have blank spots in the rendering. So, you might have:

a b c d
_ _ e f 
_ _ _ g

I already had the sequential approach implemented, so I just wanted to augment this with the ability to specify where the holes were. Here's what I came up with for a solution:

#lang scheme

;; We assume that you've put definition of define/y from
;; into
(require "../lib/")

;; This belongs in a helper file too. It's just a basic while
;; loop construct.
(define-syntax while
  (syntax-rules ()
    [(while cond expr ...)
     (let loop ()
       (when cond
         expr ...

;; Define our data
(define data '(a b c d e f g))

;; Define our layout. #t assumes we can put an element there
;; #f means we can't.
(define layout '(#t #t #t #t
                 #f #f #t #t
                 #f #f #f #t))

;; Our main program. `Data' is a list. `layout' is a function
;; that we can invoke to give us instructions on where to layout.
;; We create layout using a helper function below.
(define (do-layout data layout)  
  ;; A trivial implementation of "show" - the real system
  ;; might do something more complicated than print the data out.
  ;; Notice the `modulo 4' trick here is just to print out our sequence
  ;; propery.
  (define shown-so-far 0)
  (define (show x)
    (printf "~a " (if x x "-"))
    (set! shown-so-far (add1 shown-so-far))
    (when (zero? (modulo shown-so-far 4))

  ;; Again, render here has been kept especially simple. It just calls show.
  ;; In a "real" system, render here might change a GUI or something like that.
  (define (render value guide)     
    ;; A bit of magic happens here. We invoke (guide) to give us a clue as to whether
    ;; or not it's cool to lay out an element here. If not, then show nothing and 
    ;; try again. Essentially, we lay down one blank spot for each #f listed above.
    (while (not (guide))
           (show #f))
    ;; Finally, we know we have a valid hole, so show our value
    (show value))
  ;; The our main loop - just go through each piece of data and ask to render it.
  (let ([guide (layout->guide layout)])
    (for ([value data])
      (render value guide))))

;; A bit of magic to convert a list like:
;;  '(#t #f #t #f)
;; into a function, that when invoked, will sequentially return back
;; these values.
(define (layout->guide layout)
  (define/y (guide)
    (for-each yield layout))
  ;; [1] See note below
  (lambda ()

You can test this with the expression:

 (do-layout data layout)

The Good, The Bad And The Ugly

Overall, I like the solution above. The define/y handles all the annoyances of keeping track of whether or not my next spot is a free one. So, we'll call that the good.

There's not much bad above, as far as I can tell? (Well, besides my ridiculous example)

The ugly to me is:

;; A bit of magic to convert a list like:
;;  '(#t #f #t #f)
;; into a function, that when invoked, 
;; will sequentially return back
;; these values.
(define (layout->guide layout)
  (define/y (guide)
    (for-each yield layout))
  ;; [1] See note below
  (lambda ()

The above function has to be careful to not just create a generator, but arrange for a fresh one to be returned. Otherwise, you may have code that expects to be starting at the beginning of the sequence of generators, and yet, be at the end.

If I use this construct more, I'm going to tune this process further. Perhaps something like:

  (define/y-maker (make-foo)
    (yield 1)
    (yield 2)
    (yield 3))

The usage would be:

 (let ([foo (make-foo)])
   (list (foo) (foo) (foo)))

The above is nice, because it emphasizes that you're defining a function which returns your generator function, rather than being the generating function itself.

My guess is that someone's already done this properly, and it's probably lurking on planet, just waiting for me to use it.

Still, the above has been a great thought exercise.

No comments:

Post a Comment