[racket] A control-theory question

From: Danny Yoo (dyoo at cs.wpi.edu)
Date: Tue Nov 23 20:38:08 EST 2010

Hi everyone,

In Moby (my Racket->JS evaluator), I have a parameter that checks the
number of steps that the evaluator takes: after a certain threshold,
the evaluator temporarily yields control back to the browser, and
schedules itself for a restart.  I have a rate at which I want the
evaluator to yield --- about five times a second.  However, I don't
know how fast my evaluator actually runs per step.

My problem is to guess at the threshold that gets me closest to the
desired rate of yielding.  As of this moment, I was hardcoding that
value, but I've since realized that this is just boneheaded.
Different platforms (the phone, the desktop browser) run at different
rates.  The parameter should be dynamically determined!

I want the search to be relatively cheap and not use too many guesses.
 What I'm going for right now is a simulated-annealing search: guess
at a parameter, and adjust.  I wanted to get feedback first to see if
there was some other search or approach that is better.  Here's
essentially what I'm planning to do:

#lang racket

(define *HEAT-CUTOFF* 1)

;; find-parameter: number (number -> number) (number -> boolean) -> number
;; Search for a parameter, using the initial guess to start off.
;; Heat should be a function that's nonnegative and
;; monotonically decreasing that decays eventually to zero.
(define (find-parameter #:initial-guess initial-guess
                        #:heat-function heat
                        #:guess-too-small? too-small?
                        #:max-iterations (max-iterations 200))
  (let loop ([time 0]
             [current-guess initial-guess])
    (let ([h (heat time)])
        [(< h *HEAT-CUTOFF*)
        [(> time max-iterations)
        [(too-small? current-guess)
         (loop (add1 time)
               (+ current-guess (heat time)))]
         (loop (add1 time)
               (- current-guess (heat time)))]))))

;; exponential-decay: number
;;                           #:scale (number 1)
;;                           #:width (number 1) -> number
;; Computes an exponential decay curve; scale and width
;; are meant to stretch out the graph a bit.
(define (exponential-decay #:scale (scale 1)
                           #:width (width 1)
  (* scale (exp (- (/ x width)))))

;; guessing-game: number -> number
;; Drive find-parameter and see if it can figure out n, given
;; that it knows nothing except whether its guess is too big or small.
(define (guessing-game n)
  (find-parameter #:initial-guess 0
                  #:heat-function (lambda (x)
                                    (exponential-decay x
                                                       #:scale 50000
                                                       #:width 20))
                  #:guess-too-small? (lambda (guess)
                                       (< guess n))))

Posted on the users mailing list.